package com.yvon.service.demo.algorithm.sort;

/**
 * @author : Yvon
 * @since : 2021-10-13
 */
public class SearchTest {

    public static void main(String[] args) {
        int[] arr = {1,2,3,5,7,9,10,11};
        System.out.println("递归二分查找：" + recursionBinarySearch(arr, 7, 0, arr.length - 1 ));
        System.out.println("普通二分查找：" + commonBinarySearch(arr, 7));
    }

    /**
     * 递归二分查找
     *
     * @param arr  arr
     * @param key  关键
     * @param low  低
     * @param high 高
     * @return int
     * @author : Yvon / 2021-10-13
     */
    public static int recursionBinarySearch(int[] arr, int key ,int low, int high) {
        if (arr[low] > key || arr[high] < key || high < low) {
            return -1;
        }
        int middle = (low + high) / 2;

        if (arr[middle] < key) {
            return recursionBinarySearch(arr, key, middle + 1, high);
        }else if (arr[middle] > key) {
            return recursionBinarySearch(arr, key, low, middle -1);
        }else {
            return middle;
        }
    }

    /**
     * 常见的二分查找
     *
     * @param arr arr
     * @param key 关键
     * @return int
     * @author : Yvon / 2021-10-13
     */
    public static int commonBinarySearch(int[] arr, int key) {
        int low = 0;
        int high = arr.length -1 ;
        int middle = 0;

        if (arr[low] > key || arr[high] < key || high < low) {
            return -1;
        }
        while (low <= high) {
            middle = (low + high) / 2;
            if (arr[middle] < key) {
                low = middle + 1;
            }else if (arr[middle] > key) {
                high = middle -1;
            }else {
                return middle;
            }
        }
        return -1;
    }
}
